跳到主要内容

07 - 映射TMap

本文主要说明了UE5中有关容器类映射TMap的相关概念和常见操作。

TMap​

TMap主要由两个类型定义（一个键类型和一个值类型），以关联对（TPair<KeyType, ValueType>）的形式存储在映射中。TMap是一种哈希容器，也就是说键类型必须支持GetTypeHash()函数，并提供operator==来比较每个键是否等值。

此外，内存中TMap元素的相对排序既不可靠也不稳定，对这些元素进行迭代很可能会使它们返回的顺序和它们添加的顺序有所不同，这些元素也不太可能在内存中连续排列。

TMultiMap​

TMap只支持存储一个相同的键，重复存储将导致值的替换。而TMultiMap支持存储多个相同的键。

声明​

声明一个TMap的方法如下：

TMap<int32, FString> FruitMap;

添加元素​

和TArray类似，可以用Add(K, V)，Emplace(K, V)往TMap中添加元素；可用Append(Map2)将映射Map2中的所有元素移动到调用者中。

要想获取值，可通过operator[]以键为索引查找对应的值。

遍历元素​

TMap支持基于范围和基于迭代器的遍历：

// 基于范围的遍历:
for (auto& Elem : FruitMap)
{
    FPlatformMisc::LocalPrint(
        *FString::Printf(
            TEXT("(%d, \"%s\")\n"),
            Elem.Key,
            *Elem.Value
        )
    );
}

// 基于迭代器的遍历:
// CreateIterator():      读写访问
// CreateConstIterator(): 只读访问
for (auto It = FruitMap.CreateConstIterator(); It; ++It)
{
    FPlatformMisc::LocalPrint(
        *FString::Printf(
            TEXT("(%d, \"%s\")\n"),
            It.Key(),   // same as It->Key
            *It.Value() // same as *It->Value
        )
    );
}

排序​

如果之后不再对映射进行修改，可通过KeySort()和ValueSort()函数对映射分别按键和值排序：

FruitMap.KeySort([](int32 A, int32 B) {
    return A > B; // sort keys in reverse
});
 
FruitMap.ValueSort([](const FString& A, const FString& B) {
        return A.Len() < B.Len(); // sort strings by length
});

查询​

TMap还提供了一系列查询函数，方便用户进行相关操作：

  • 询问映射属性：
函数用途
Num()确认映射中保存的元素数量
Contains()确认映射中是否包含特定键
GenerateKeyArray()获取映射键的数组
GenerateValueArray()获取映射值的数组
CountBytes()和GetAllocatedSize()用于估计内部数组的当前内存使用情况
Dump()输出关于映射内容的实现信息，用于调试
  • 键值查询类：
函数用途
Find()如果映射包含该键，返回指向元素值的指针
FindOrAdd()找不到就用该键和默认值创建新元素，并且返回值的引用
FindRef()找不到不会创建新元素，而是返回临时构建的默认值；找到则返回对应值的副本
FindKey()寻找并返回首个拥有该值的键的指针，找不到返回空指针

移除​

TMap提供了一系列移除函数：

函数用途
Remove()根据键移除指定元素，返回移除元素的数量
FindAndRemoveChecked()根据键移除指定元素，返回移除元素值；找不到会触发Assert()
RemoveAndCopyValue()根据键移除指定元素，将值复制到引用参数中，最后以bool返回是否成功
Empty()和Reset()同TArray中的相关函数

需要注意的是，移除一个元素后，TMap仍会保留该元素之前所在的内存空间。

运算符​

TMap提供如下运算符：

  • operator=：拷贝赋值；
  • MoveTemp()：移动赋值；

内存管理​

Slack​

和TArray类似，TMap也有Slack这个概念。Slack优化了将新元素添加到映射的过程，因为可以使用它预分配的内存，而不是分配新内存；在移除元素时也十分实用，因为系统不需要真正取消被移除元素的内存分配。

Reserve()，Reset()和Empty()函数的用途和TArray类似。

需要注意的是Shrink()函数的使用方法：先Compact()，后Shrink()。因为Shrink()只会移除容器末端的Slack，容器元素间的Slack它无法移除，而Compact()则会整理这些空白空间至容器末尾。

编写KeyFuncs​

KeyFuncs是最后一个TMap模板参数，该参数告知映射如何从元素类型获取键，如何比较两个键是否相等，以及如何对键进行哈希计算。如果键类型是自定义的类或结构体，就需要为它自行编写KeyFuncs。

要为键编写KeyFuncs，需要定义两个类型别名和三个静态函数：

类型别名说明
KeyInitType传递键的类型
ElementInitType传递元素的类型
静态函数说明
KeyInitType GetSetKey(ElementInitType Element)返回元素的键
bool Matches(KeyInitType A, KeyInitType B)返回A == B的结果
uint32 GetKeyHash(KeyInitType Key)返回Key的哈希值

这里以自定义结构体类MyStruct为例：

struct FMyStruct
{
    // String which identifies our key
    FString UniqueID;

    // Some state which doesn't affect struct identity
    float SomeFloat;

    explicit FMyStruct(float InFloat)
        : UniqueID (FGuid::NewGuid().ToString())
            , SomeFloat(InFloat)
        {

        }
};

它的KeyFuncs如下：

template <typename ValueType>
struct TMyStructMapKeyFuncs :
        BaseKeyFuncs<
            TPair<FMyStruct, ValueType>,
            FString
        >
{
 
private:
    typedef BaseKeyFuncs<
        TPair<FMyStruct, ValueType>,
        FString
    > Super;
 
public:
    typedef typename Super::ElementInitType ElementInitType;
    typedef typename Super::KeyInitType     KeyInitType;

    static KeyInitType GetSetKey(ElementInitType Element)
    {
        return Element.Key.UniqueID;
    }

    static bool Matches(KeyInitType A, KeyInitType B)
    {
        return A.Compare(B, ESearchCase::CaseSensitive) == 0;
    }

    static uint32 GetKeyHash(KeyInitType Key)
    {
        return FCrc::StrCrc32(*Key);
    }
};

可以看到，创建自定义KeyFuncs的一般步骤如下：

  1. 继承BaseKeyFuncs（因为它定义了KeyInitType，ElementInitType等类型），它使用两个模板参数：
    • 映射的元素类型：即TPair<KeyType, ValueType>，这里使用FMyStruct带入参数KeyType，使用KeyFuncs的模板参数ValueType带入ValueType以保证泛用性。
    • KeyFuncs专用的键类型：这里使用FMyStruct::UniqueID作为判等的依据，因此是FString。
  2. 定义两个类型别名：上述代码中Super相关操作。
  3. 实现三个静态函数：
    • GetSetKey()：返回专用的键类型，这里是FMyStruct::UniqueID；
    • Matches()：判等专用的键类型，这里是比较两个FString类型；
    • GetKeyHash()：计算专用键的哈希值，这里是FString的哈希值；

最后就能创建KeyType为FMyStruct类型，ValueType为任意类型的TMap了：

TMap<
    FMyStruct,
int32,
FDefaultSetAllocator,
TMyStructMapKeyFuncs<int32>
    > MyMapToInt32;

// Add some elements
MyMapToInt32.Add(FMyStruct(3.14f), 5);
MyMapToInt32.Add(FMyStruct(1.23f), 2);
// MyMapToInt32 == [
//     {
//         Key: {
//             UniqueID:  "D06AABBA466CAA4EB62D2F97936274E4",
//             SomeFloat: 3.14f
//         },
//         Value: 5
//    },
//     {
//         Key: {
//             UniqueID:  "0661218447650259FD4E33AD6C9C5DCB",
//             SomeFloat: 1.23f
//         },
//         Value: 5
//    }
// ]

参考资料​